# 递归
def max_value(lists, i, j):
    if i == 0 and j == 0:
        return lists[i][j]
    elif i == 0 and j != 0:
        return lists[i][j] + max_value(lists, i, j - 1)
    elif i != 0 and j == 0:
        return lists[i][j] + max_value(lists, i - 1, j)
    else:
        right = max_value(lists, i - 1, j) + lists[i][j]
        upper = max_value(lists, i, j - 1) + lists[i][j]
        return max(right, upper)


def to_bottom_max(lists, r, c):
    if r == len(lists) - 1:
        return lists[r][c]
    else:
        return to_bottom_max(lists, r + 1, c) + max(
            lists[r + 1][c], lists[r + 1][c + 1]
        )


def main():
    a = [[1, 10, 3, 8], [12, 2, 9, 6], [5, 7, 4, 11], [3, 7, 16, 5]]
    b = [
        [7, 0, 0, 0, 0],
        [3, 8, 0, 0, 0],
        [8, 1, 0, 0, 0],
        [2, 7, 4, 4, 0],
        [2, 5, 2, 6, 5],
    ]
    print(to_bottom_max(b, 0, 0))


if __name__ == "__main__":
    main()
